unit heContnrs_BTreeMap_test;

{$mode objfpc}{$H+}

interface

uses
  fpcunit,
  heContnrs,
  heContnrs_test;

type

  TBTreeMapIntKey = type Integer;
  TBTreeMapIntValue = type Integer;

  TBTreeMapStrKey = type String;
  TBTreeMapStrValue = type String;

  { TTestBTreeMapInt }

  _TTestBTreeMapInt = specialize TheBTreeMap<TBTreeMapIntKey, TBTreeMapIntValue>;
  TTestBTreeMapInt = class(_TTestBTreeMapInt)
  private
    procedure RunInheritedMissingKeyValue;
  protected
    function MissingKeyValue(const AKey: TBTreeMapIntKey): TBTreeMapIntValue; override;
  public
    constructor Create(const AKIndex: Integer = 64; const AKData: Integer = 32);
  end;

  { TTestBTreeMapStr }

  _TTestBTreeMapStr = specialize TheBTreeMap<TBTreeMapStrKey, TBTreeMapStrValue>;
  TTestBTreeMapStr = class(_TTestBTreeMapStr)
  private
    procedure RunInheritedMissingKeyValue;
  protected
    function MissingKeyValue(const AKey: TBTreeMapStrKey): TBTreeMapStrValue; override;
  public
    constructor Create(const AKIndex: Integer = 64; const AKData: Integer = 32);
  end;

  TCmpBTreeMapIntKey = type Integer;
  TCmpBTreeMapIntValue = type Integer;

  TCmpBTreeMapStrKey = type String;
  TCmpBTreeMapStrValue = type String;

  { TTestCmpBTreeMapInt }

  _TTestCmpBTreeMapInt = specialize TheCmpBTreeMap<TCmpBTreeMapIntKey, TCmpBTreeMapIntValue>;
  TTestCmpBTreeMapInt = class(_TTestCmpBTreeMapInt)
  private
    procedure RunInheritedMissingKeyValue;
  protected
    function MissingKeyValue(const AKey: TCmpBTreeMapIntKey): TCmpBTreeMapIntValue; override;
  public
    constructor Create(const AKIndex: Integer = 64; const AKData: Integer = 32);
    function Compare(const A, B: TCmpBTreeMapIntKey): Integer; override;
  end;

  { TTestCmpBTreeMapStr }

  _TTestCmpBTreeMapStr = specialize TheCmpBTreeMap<TCmpBTreeMapStrKey, TCmpBTreeMapStrValue>;
  TTestCmpBTreeMapStr = class(_TTestCmpBTreeMapStr)
  private
    procedure RunInheritedMissingKeyValue;
  protected
    function MissingKeyValue(const AKey: TCmpBTreeMapStrKey): TCmpBTreeMapStrValue; override;
  public
    constructor Create(const AKIndex: Integer = 64; const AKData: Integer = 32);
    function Compare(const A, B: TCmpBTreeMapStrKey): Integer; override;
  end;

  ITestCmpBTreeMapInterfaceKey = type IInterface;
  ITestCmpBTreeMapInterfaceValue = type IInterface;

  { TTestCmpBTreeMapInterface }

  _TTestCmpBTreeMapInterface = specialize TheCmpBTreeMap<ITestCmpBTreeMapInterfaceKey, ITestCmpBTreeMapInterfaceValue>;
  TTestCmpBTreeMapInterface = class(_TTestCmpBTreeMapInterface)
  private
    procedure RunInheritedMissingKeyValue;
  protected
    function MissingKeyValue(const AKey: ITestCmpBTreeMapInterfaceKey): ITestCmpBTreeMapInterfaceValue; override;
  public
    constructor Create(const AKIndex: Integer = 64; const AKData: Integer = 32);
    function Compare(const A, B: ITestCmpBTreeMapInterfaceKey): Integer; override;
  end;

  { TTestObjectBTreeMap }

  _TTestObjectBTreeMap = specialize TheObjectBTreeMap<String, TTracedObject>;
  TTestObjectBTreeMap = class(_TTestObjectBTreeMap)
  private
    procedure RunInheritedMissingKeyValue;
  protected
    function MissingKeyValue(const AKey: String): TTracedObject; override;
  public
    constructor Create(const AKIndex: Integer = 64; const AKData: Integer = 32; const AOwnValues: Boolean = True);
    function Compare(const A, B: String): Integer; override;
  end;

  { TheBTreeMapTest }

  generic TheBTreeMapTest<TBTreeMap, TKey, TValue> = class(TTestCase)
  private
    Map: TBTreeMap;
  protected
    procedure Done(const V: TValue); virtual;
    function Int2Key(const N: Integer): TKey; virtual; // abstract;
    function Key2Int(const K: TKey): Integer; virtual; // abstract;
    function Int2Value(const N: Integer): TValue; virtual; // abstract;
    function Value2Int(const V: TValue): Integer; virtual; // abstract;
    procedure SetUp; override;
    procedure TearDown; override;
  published
    procedure TestCreate;
    procedure TestCount;
    procedure TestMissingKeyValue;
    procedure TestClear;
    procedure TestFirst;
    procedure TestFirstKey;
    procedure TestLast;
    procedure TestLastKey;
    procedure TestExtract;
    procedure TestDelete;
    procedure TestMap;
    procedure TestGet;
    procedure TestPut;
    procedure TestPut2;
    procedure TestMix;
  end;

  { TheIntBTreeMapTest }

  _TheIntBTreeMapTest = specialize TheBTreeMapTest<TTestBTreeMapInt, Integer, Integer>;
  TheIntBTreeMapTest = class(_TheIntBTreeMapTest)
  protected
    function Int2Key(const N: Integer): Integer; override;
    function Key2Int(const K: Integer): Integer; override;
    function Int2Value(const N: Integer): Integer; override;
    function Value2Int(const V: Integer): Integer; override;
  published
    procedure TestKeys;
    procedure TestKeysReversed;
    procedure TestValues;
    procedure TestValuesReversed;
    procedure TestGetRangeKeys;
    procedure TestGetRange;
  end;

  { TheStrBTreeMapTest }

  _TheStrBTreeMapTest = specialize TheBTreeMapTest<TTestBTreeMapStr, String, String>;
  TheStrBTreeMapTest = class(_TheStrBTreeMapTest)
  protected
    function Int2Key(const N: Integer): String; override;
    function Key2Int(const K: String): Integer; override;
    function Int2Value(const N: Integer): String; override;
    function Value2Int(const V: String): Integer; override;
  published
    procedure TestKeys;
    procedure TestKeysReversed;
    procedure TestValues;
    procedure TestValuesReversed;
    procedure TestGetRangeKeys;
    procedure TestGetRange;
  end;

  { TheIntCmpBTreeMapTest }

  _TheIntCmpBTreeMapTest = specialize TheBTreeMapTest<TTestCmpBTreeMapInt, Integer, Integer>;
  TheIntCmpBTreeMapTest = class(_TheIntCmpBTreeMapTest)
  protected
    function Int2Key(const N: Integer): Integer; override;
    function Key2Int(const K: Integer): Integer; override;
    function Int2Value(const N: Integer): Integer; override;
    function Value2Int(const V: Integer): Integer; override;
  published
    procedure TestKeys;
    procedure TestKeysReversed;
    procedure TestValues;
    procedure TestValuesReversed;
    procedure TestGetRangeKeys;
    procedure TestGetRange;
  end;

  { TheStrCmpBTreeMapTest }

  _TheStrCmpBTreeMapTest = specialize TheBTreeMapTest<TTestCmpBTreeMapStr, String, String>;
  TheStrCmpBTreeMapTest = class(_TheStrCmpBTreeMapTest)
  protected
    function Int2Key(const N: Integer): String; override;
    function Key2Int(const K: String): Integer; override;
    function Int2Value(const N: Integer): String; override;
    function Value2Int(const V: String): Integer; override;
  published
    procedure TestKeys;
    procedure TestKeysReversed;
    procedure TestValues;
    procedure TestValuesReversed;
    procedure TestGetRangeKeys;
    procedure TestGetRange;
  end;

  { TheInterfaceCmpBTreeMapTest }

  _TheInterfaceCmpBTreeMapTest = specialize TheBTreeMapTest<TTestCmpBTreeMapInterface, ITestCmpBTreeMapInterfaceKey, ITestCmpBTreeMapInterfaceValue>;
  TheInterfaceCmpBTreeMapTest = class(_TheInterfaceCmpBTreeMapTest)
  protected
    function Int2Key(const N: Integer): ITestCmpBTreeMapInterfaceKey; override;
    function Key2Int(const K: ITestCmpBTreeMapInterfaceKey): Integer; override;
    function Int2Value(const N: Integer): ITestCmpBTreeMapInterfaceValue; override;
    function Value2Int(const V: ITestCmpBTreeMapInterfaceValue): Integer; override;
  published
    procedure TestKeys;
    procedure TestKeysReversed;
    procedure TestValues;
    procedure TestValuesReversed;
    procedure TestGetRangeKeys;
    procedure TestGetRange;
  end;

  { TheObjectBTreeMapTest }

  _TheObjectBTreeMapTest = specialize TheBTreeMapTest<TTestObjectBTreeMap, String, TTracedObject>;
  TheObjectBTreeMapTest = class(_TheObjectBTreeMapTest)
  protected
    procedure Done(const V: TTracedObject); override;
    function Int2Key(const N: Integer): String; override;
    function Key2Int(const K: String): Integer; override;
    function Int2Value(const N: Integer): TTracedObject; override;
    function Value2Int(const V: TTracedObject): Integer; override;
  published
    procedure TestCreate2;
    procedure TestCreate3;
    procedure TestKeys;
    procedure TestKeysReversed;
    procedure TestValues;
    procedure TestValuesReversed;
    procedure TestGetRangeKeys;
    procedure TestGetRange;
  end;

implementation

uses
  Classes,
  SysUtils,
  testregistry;

function I2S(N: Integer): String;
var
  R: LongRec absolute N;
  I: Integer;
begin
  SetLength(Result, Succ(High(R.Bytes)));
  R.Bytes[High(R.Bytes)] := R.Bytes[High(R.Bytes)] xor $80;
  for I := 0 to High(R.Bytes) do
    PByte(Result)[I] := R.Bytes[High(R.Bytes) - I];
end;

function S2I(const S: String): Integer;
var
  R: LongRec absolute Result;
  I: Integer;
begin
  for I := 0 to High(R.Bytes) do
    R.Bytes[High(R.Bytes) - I] := PByte(S)[I];
  R.Bytes[High(R.Bytes)] := R.Bytes[High(R.Bytes)] xor $80;
end;

{ TTestBTreeMapInt }

procedure TTestBTreeMapInt.RunInheritedMissingKeyValue;
begin
  inherited MissingKeyValue(0);
end;

function TTestBTreeMapInt.MissingKeyValue(const AKey: TBTreeMapIntKey): TBTreeMapIntValue;
begin
  Assert(AKey = AKey); // hint off
  Result := Low(Integer);
end;

constructor TTestBTreeMapInt.Create(const AKIndex: Integer; const AKData: Integer);
begin
  inherited;
end;

{ TTestBTreeMapStr }

procedure TTestBTreeMapStr.RunInheritedMissingKeyValue;
begin
  inherited MissingKeyValue('<missing key>');
end;

function TTestBTreeMapStr.MissingKeyValue(const AKey: TBTreeMapStrKey): TBTreeMapStrValue;
begin
  Assert(AKey = AKey); // hint off
  Result := I2S(Low(Integer));
end;

constructor TTestBTreeMapStr.Create(const AKIndex: Integer; const AKData: Integer);
begin
  inherited;
end;

{ TTestCmpBTreeMapInt }

procedure TTestCmpBTreeMapInt.RunInheritedMissingKeyValue;
begin
  inherited MissingKeyValue(0);
end;

function TTestCmpBTreeMapInt.MissingKeyValue(const AKey: TCmpBTreeMapIntKey): TCmpBTreeMapIntValue;
begin
  Assert(AKey = AKey); // hint off
  Result := Low(Integer);
end;

constructor TTestCmpBTreeMapInt.Create(const AKIndex: Integer; const AKData: Integer);
begin
  inherited;
end;

function TTestCmpBTreeMapInt.Compare(const A, B: TCmpBTreeMapIntKey): Integer;
begin
  Result := A - B;
end;

{ TTestCmpBTreeMapStr }

procedure TTestCmpBTreeMapStr.RunInheritedMissingKeyValue;
begin
  inherited MissingKeyValue('<missing key>');
end;

function TTestCmpBTreeMapStr.MissingKeyValue(const AKey: TCmpBTreeMapStrKey): TCmpBTreeMapStrValue;
begin
  Assert(AKey = AKey); // hint off
  Result := I2S(Low(Integer));
end;

constructor TTestCmpBTreeMapStr.Create(const AKIndex: Integer; const AKData: Integer);
begin
  inherited;
end;

function TTestCmpBTreeMapStr.Compare(const A, B: TCmpBTreeMapStrKey): Integer;
begin
  Result := CompareStr(A, B);
end;

{ TTestCmpBTreeMapInterface }

procedure TTestCmpBTreeMapInterface.RunInheritedMissingKeyValue;
var AKey: ITestCmpBTreeMapInterfaceKey;
begin
  AKey := nil;
  inherited MissingKeyValue(AKey);
end;

function TTestCmpBTreeMapInterface.MissingKeyValue(const AKey: ITestCmpBTreeMapInterfaceKey): ITestCmpBTreeMapInterfaceValue;
begin
  Assert(AKey = AKey); // hint off
  Result := TInterfacedTracedObject.Create(nil, Low(Integer)) as ITestCmpBTreeMapInterfaceValue;
end;

constructor TTestCmpBTreeMapInterface.Create(const AKIndex: Integer; const AKData: Integer);
begin
  inherited;
end;

function TTestCmpBTreeMapInterface.Compare(const A, B: ITestCmpBTreeMapInterfaceKey): Integer;
begin
  Result := (A as TInterfacedTracedObject).ID - (B as TInterfacedTracedObject).ID;
end;

{ TTestObjectBTreeMap }

procedure TTestObjectBTreeMap.RunInheritedMissingKeyValue;
begin
  inherited MissingKeyValue('<missing key>');
end;

function TTestObjectBTreeMap.MissingKeyValue(const AKey: String): TTracedObject;
begin
  Assert(AKey = AKey); // hint off
  Result := nil;
end;

constructor TTestObjectBTreeMap.Create(const AKIndex: Integer; const AKData: Integer; const AOwnValues: Boolean);
begin
  inherited Create(AOwnValues, AKIndex, AKData);
end;

function TTestObjectBTreeMap.Compare(const A, B: String): Integer;
begin
  Result := CompareStr(A, B);
end;

{ TheIntBTreeMapTest }

function TheIntBTreeMapTest.Int2Key(const N: Integer): Integer;
begin
  Result := N;
end;

function TheIntBTreeMapTest.Key2Int(const K: Integer): Integer;
begin
  Result := K;
end;

function TheIntBTreeMapTest.Int2Value(const N: Integer): Integer;
begin
  Result := N;
end;

function TheIntBTreeMapTest.Value2Int(const V: Integer): Integer;
begin
  Result := V;
end;

procedure TheIntBTreeMapTest.TestKeys;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Keys do begin
      AssertEquals('V', Value2Int(A[J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntBTreeMapTest.TestKeysReversed;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.KeysReversed do begin
      AssertEquals('V', Value2Int(A[I - J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntBTreeMapTest.TestValues;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Values do begin
      AssertEquals('V', Value2Int(A[J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntBTreeMapTest.TestValuesReversed;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.ValuesReversed do begin
      AssertEquals('V', Value2Int(A[I - J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntBTreeMapTest.TestGetRangeKeys;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TKey;
  begin
    I := 0;
    for V in Map.RangeKeys[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Key2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheIntBTreeMapTest.TestGetRangeKeys;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

procedure TheIntBTreeMapTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TValue;
  begin
    I := 0;
    for V in Map.Range[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Value2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheIntBTreeMapTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [200, 250]);
      Verify(19, 30, [200, 250, 300]);
      Verify(19, 31, [200, 250, 300]);
      Verify(20, 29, [200, 250]);
      Verify(20, 30, [200, 250, 300]);
      Verify(20, 31, [200, 250, 300]);
      Verify(21, 29, [250]);
      Verify(21, 30, [250, 300]);
      Verify(21, 31, [250, 300]);

      Verify(19, 24, [200]);
      Verify(19, 25, [200, 250]);
      Verify(19, 26, [200, 250]);
      Verify(20, 24, [200]);
      Verify(20, 25, [200, 250]);
      Verify(20, 26, [200, 250]);
      Verify(21, 24, []);
      Verify(21, 25, [250]);
      Verify(21, 26, [250]);

      Verify(29, 19, [250, 200]);
      Verify(29, 20, [250, 200]);
      Verify(29, 21, [250]);
      Verify(30, 19, [300, 250, 200]);
      Verify(30, 20, [300, 250, 200]);
      Verify(30, 21, [300, 250]);
      Verify(31, 19, [300, 250, 200]);
      Verify(31, 20, [300, 250, 200]);
      Verify(31, 21, [300, 250]);

      Verify(24, 19, [200]);
      Verify(24, 20, [200]);
      Verify(24, 21, []);
      Verify(25, 19, [250, 200]);
      Verify(25, 20, [250, 200]);
      Verify(25, 21, [250]);
      Verify(26, 19, [250, 200]);
      Verify(26, 20, [250, 200]);
      Verify(26, 21, [250]);
    end;
end;

{ TheStrBTreeMapTest }

function TheStrBTreeMapTest.Int2Key(const N: Integer): String;
begin
  Result := I2S(N);
end;

function TheStrBTreeMapTest.Key2Int(const K: String): Integer;
begin
  Result := S2I(K);
end;

function TheStrBTreeMapTest.Int2Value(const N: Integer): String;
begin
  Result := I2S(N);
end;

function TheStrBTreeMapTest.Value2Int(const V: String): Integer;
begin
  Result := S2I(V);
end;

procedure TheStrBTreeMapTest.TestKeys;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Keys do begin
      AssertEquals('V', Value2Int(A[J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrBTreeMapTest.TestKeysReversed;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.KeysReversed do begin
      AssertEquals('V', Value2Int(A[I - J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrBTreeMapTest.TestValues;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Values do begin
      AssertEquals('V', Value2Int(A[J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrBTreeMapTest.TestValuesReversed;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.ValuesReversed do begin
      AssertEquals('V', Value2Int(A[I - J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrBTreeMapTest.TestGetRangeKeys;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TKey;
  begin
    I := 0;
    for V in Map.RangeKeys[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Key2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheStrBTreeMapTest.TestGetRangeKeys;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

procedure TheStrBTreeMapTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TValue;
  begin
    I := 0;
    for V in Map.Range[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Value2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheStrBTreeMapTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [200, 250]);
      Verify(19, 30, [200, 250, 300]);
      Verify(19, 31, [200, 250, 300]);
      Verify(20, 29, [200, 250]);
      Verify(20, 30, [200, 250, 300]);
      Verify(20, 31, [200, 250, 300]);
      Verify(21, 29, [250]);
      Verify(21, 30, [250, 300]);
      Verify(21, 31, [250, 300]);

      Verify(19, 24, [200]);
      Verify(19, 25, [200, 250]);
      Verify(19, 26, [200, 250]);
      Verify(20, 24, [200]);
      Verify(20, 25, [200, 250]);
      Verify(20, 26, [200, 250]);
      Verify(21, 24, []);
      Verify(21, 25, [250]);
      Verify(21, 26, [250]);

      Verify(29, 19, [250, 200]);
      Verify(29, 20, [250, 200]);
      Verify(29, 21, [250]);
      Verify(30, 19, [300, 250, 200]);
      Verify(30, 20, [300, 250, 200]);
      Verify(30, 21, [300, 250]);
      Verify(31, 19, [300, 250, 200]);
      Verify(31, 20, [300, 250, 200]);
      Verify(31, 21, [300, 250]);

      Verify(24, 19, [200]);
      Verify(24, 20, [200]);
      Verify(24, 21, []);
      Verify(25, 19, [250, 200]);
      Verify(25, 20, [250, 200]);
      Verify(25, 21, [250]);
      Verify(26, 19, [250, 200]);
      Verify(26, 20, [250, 200]);
      Verify(26, 21, [250]);
    end;
end;

{ TheIntCmpBTreeMapTest }

function TheIntCmpBTreeMapTest.Int2Key(const N: Integer): Integer;
begin
  Result := N;
end;

function TheIntCmpBTreeMapTest.Key2Int(const K: Integer): Integer;
begin
  Result := K;
end;

function TheIntCmpBTreeMapTest.Int2Value(const N: Integer): Integer;
begin
  Result := N;
end;

function TheIntCmpBTreeMapTest.Value2Int(const V: Integer): Integer;
begin
  Result := V;
end;

procedure TheIntCmpBTreeMapTest.TestKeys;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Keys do begin
      AssertEquals('V', Value2Int(A[J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntCmpBTreeMapTest.TestKeysReversed;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.KeysReversed do begin
      AssertEquals('V', Value2Int(A[I - J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntCmpBTreeMapTest.TestValues;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Values do begin
      AssertEquals('V', Value2Int(A[J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntCmpBTreeMapTest.TestValuesReversed;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.ValuesReversed do begin
      AssertEquals('V', Value2Int(A[I - J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheIntCmpBTreeMapTest.TestGetRangeKeys;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TKey;
  begin
    I := 0;
    for V in Map.RangeKeys[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Key2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheIntCmpBTreeMapTest.TestGetRangeKeys;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

procedure TheIntCmpBTreeMapTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TValue;
  begin
    I := 0;
    for V in Map.Range[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Value2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheIntCmpBTreeMapTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [200, 250]);
      Verify(19, 30, [200, 250, 300]);
      Verify(19, 31, [200, 250, 300]);
      Verify(20, 29, [200, 250]);
      Verify(20, 30, [200, 250, 300]);
      Verify(20, 31, [200, 250, 300]);
      Verify(21, 29, [250]);
      Verify(21, 30, [250, 300]);
      Verify(21, 31, [250, 300]);

      Verify(19, 24, [200]);
      Verify(19, 25, [200, 250]);
      Verify(19, 26, [200, 250]);
      Verify(20, 24, [200]);
      Verify(20, 25, [200, 250]);
      Verify(20, 26, [200, 250]);
      Verify(21, 24, []);
      Verify(21, 25, [250]);
      Verify(21, 26, [250]);

      Verify(29, 19, [250, 200]);
      Verify(29, 20, [250, 200]);
      Verify(29, 21, [250]);
      Verify(30, 19, [300, 250, 200]);
      Verify(30, 20, [300, 250, 200]);
      Verify(30, 21, [300, 250]);
      Verify(31, 19, [300, 250, 200]);
      Verify(31, 20, [300, 250, 200]);
      Verify(31, 21, [300, 250]);

      Verify(24, 19, [200]);
      Verify(24, 20, [200]);
      Verify(24, 21, []);
      Verify(25, 19, [250, 200]);
      Verify(25, 20, [250, 200]);
      Verify(25, 21, [250]);
      Verify(26, 19, [250, 200]);
      Verify(26, 20, [250, 200]);
      Verify(26, 21, [250]);
    end;
end;

{ TheStrCmpBTreeMapTest }

function TheStrCmpBTreeMapTest.Int2Key(const N: Integer): String;
begin
  Result := I2S(N);
end;

function TheStrCmpBTreeMapTest.Key2Int(const K: String): Integer;
begin
  Result := S2I(K);
end;

function TheStrCmpBTreeMapTest.Int2Value(const N: Integer): String;
begin
  Result := I2S(N);
end;

function TheStrCmpBTreeMapTest.Value2Int(const V: String): Integer;
begin
  Result := S2I(V);
end;

procedure TheStrCmpBTreeMapTest.TestKeys;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Keys do begin
      AssertEquals('V', Value2Int(A[J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrCmpBTreeMapTest.TestKeysReversed;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.KeysReversed do begin
      AssertEquals('V', Value2Int(A[I - J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrCmpBTreeMapTest.TestValues;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Values do begin
      AssertEquals('V', Value2Int(A[J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrCmpBTreeMapTest.TestValuesReversed;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.ValuesReversed do begin
      AssertEquals('V', Value2Int(A[I - J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheStrCmpBTreeMapTest.TestGetRangeKeys;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TKey;
  begin
    I := 0;
    for V in Map.RangeKeys[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Key2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheStrCmpBTreeMapTest.TestGetRangeKeys;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

procedure TheStrCmpBTreeMapTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TValue;
  begin
    I := 0;
    for V in Map.Range[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Value2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheStrCmpBTreeMapTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [200, 250]);
      Verify(19, 30, [200, 250, 300]);
      Verify(19, 31, [200, 250, 300]);
      Verify(20, 29, [200, 250]);
      Verify(20, 30, [200, 250, 300]);
      Verify(20, 31, [200, 250, 300]);
      Verify(21, 29, [250]);
      Verify(21, 30, [250, 300]);
      Verify(21, 31, [250, 300]);

      Verify(19, 24, [200]);
      Verify(19, 25, [200, 250]);
      Verify(19, 26, [200, 250]);
      Verify(20, 24, [200]);
      Verify(20, 25, [200, 250]);
      Verify(20, 26, [200, 250]);
      Verify(21, 24, []);
      Verify(21, 25, [250]);
      Verify(21, 26, [250]);

      Verify(29, 19, [250, 200]);
      Verify(29, 20, [250, 200]);
      Verify(29, 21, [250]);
      Verify(30, 19, [300, 250, 200]);
      Verify(30, 20, [300, 250, 200]);
      Verify(30, 21, [300, 250]);
      Verify(31, 19, [300, 250, 200]);
      Verify(31, 20, [300, 250, 200]);
      Verify(31, 21, [300, 250]);

      Verify(24, 19, [200]);
      Verify(24, 20, [200]);
      Verify(24, 21, []);
      Verify(25, 19, [250, 200]);
      Verify(25, 20, [250, 200]);
      Verify(25, 21, [250]);
      Verify(26, 19, [250, 200]);
      Verify(26, 20, [250, 200]);
      Verify(26, 21, [250]);
    end;
end;

{ TheInterfaceCmpBTreeMapTest }

function TheInterfaceCmpBTreeMapTest.Int2Key(const N: Integer): ITestCmpBTreeMapInterfaceKey;
begin
  Result := TInterfacedTracedObject.Create(nil, N) as ITestCmpBTreeMapInterfaceKey;
end;

function TheInterfaceCmpBTreeMapTest.Key2Int(const K: ITestCmpBTreeMapInterfaceKey): Integer;
begin
  Result := (K as TInterfacedTracedObject).ID;
end;

function TheInterfaceCmpBTreeMapTest.Int2Value(const N: Integer): ITestCmpBTreeMapInterfaceValue;
begin
  Result := TInterfacedTracedObject.Create(nil, N) as ITestCmpBTreeMapInterfaceValue;
end;

function TheInterfaceCmpBTreeMapTest.Value2Int(const V: ITestCmpBTreeMapInterfaceValue): Integer;
begin
  Result := (V as TInterfacedTracedObject).ID;
end;

procedure TheInterfaceCmpBTreeMapTest.TestKeys;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Keys do begin
      AssertEquals('V', Value2Int(A[J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheInterfaceCmpBTreeMapTest.TestKeysReversed;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.KeysReversed do begin
      AssertEquals('V', Value2Int(A[I - J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheInterfaceCmpBTreeMapTest.TestValues;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Values do begin
      AssertEquals('V', Value2Int(A[J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheInterfaceCmpBTreeMapTest.TestValuesReversed;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.ValuesReversed do begin
      AssertEquals('V', Value2Int(A[I - J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheInterfaceCmpBTreeMapTest.TestGetRangeKeys;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TKey;
  begin
    I := 0;
    for V in Map.RangeKeys[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Key2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheInterfaceCmpBTreeMapTest.TestGetRangeKeys;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

procedure TheInterfaceCmpBTreeMapTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TValue;
  begin
    I := 0;
    for V in Map.Range[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Value2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheInterfaceCmpBTreeMapTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [200, 250]);
      Verify(19, 30, [200, 250, 300]);
      Verify(19, 31, [200, 250, 300]);
      Verify(20, 29, [200, 250]);
      Verify(20, 30, [200, 250, 300]);
      Verify(20, 31, [200, 250, 300]);
      Verify(21, 29, [250]);
      Verify(21, 30, [250, 300]);
      Verify(21, 31, [250, 300]);

      Verify(19, 24, [200]);
      Verify(19, 25, [200, 250]);
      Verify(19, 26, [200, 250]);
      Verify(20, 24, [200]);
      Verify(20, 25, [200, 250]);
      Verify(20, 26, [200, 250]);
      Verify(21, 24, []);
      Verify(21, 25, [250]);
      Verify(21, 26, [250]);

      Verify(29, 19, [250, 200]);
      Verify(29, 20, [250, 200]);
      Verify(29, 21, [250]);
      Verify(30, 19, [300, 250, 200]);
      Verify(30, 20, [300, 250, 200]);
      Verify(30, 21, [300, 250]);
      Verify(31, 19, [300, 250, 200]);
      Verify(31, 20, [300, 250, 200]);
      Verify(31, 21, [300, 250]);

      Verify(24, 19, [200]);
      Verify(24, 20, [200]);
      Verify(24, 21, []);
      Verify(25, 19, [250, 200]);
      Verify(25, 20, [250, 200]);
      Verify(25, 21, [250]);
      Verify(26, 19, [250, 200]);
      Verify(26, 20, [250, 200]);
      Verify(26, 21, [250]);
    end;
end;

{ TheObjectBTreeMapTest }

procedure TheObjectBTreeMapTest.Done(const V: TTracedObject);
begin
  V.Free;
end;

function TheObjectBTreeMapTest.Int2Key(const N: Integer): String;
begin
  Result := I2S(N);
end;

function TheObjectBTreeMapTest.Key2Int(const K: String): Integer;
begin
  Result := S2I(K);
end;

function TheObjectBTreeMapTest.Int2Value(const N: Integer): TTracedObject;
begin
  Result := TTracedObject.Create(nil, N);
end;

function TheObjectBTreeMapTest.Value2Int(const V: TTracedObject): Integer;
begin
  if V = nil then
    Exit(Low(Integer));
  Result := V.ID;
end;

procedure TheObjectBTreeMapTest.TestCreate2;
var
  Tracer: TBits;
  L: TTestObjectBTreeMap;
begin
  L := TTestObjectBTreeMap.Create;
  try
    AssertTrue(L.OwnObjects);
    Tracer := TBits.Create;
    try
      L['foo'] := TTracedObject.Create(Tracer, 1);
      L.Clear;
      AssertFalse('Item dead', Tracer[1]);
    finally
      Tracer.Free;
    end;
  finally
    L.Free;
  end;
end;

procedure TheObjectBTreeMapTest.TestCreate3;
var
  Tracer: TBits;
  L: TTestObjectBTreeMap;
  Obj: TTracedObject;
begin
  L := TTestObjectBTreeMap.Create(0, 0, False);
  try
    AssertFalse(L.OwnObjects);
    Tracer := TBits.Create;
    try
      Obj := TTracedObject.Create(Tracer, 1);
      try
        L['foo'] := Obj;
        L.Clear;
        AssertTrue('Item alive', Tracer[1]);
      finally
        Obj.Free;
      end;
    finally
      Tracer.Free;
    end;
  finally
    L.Free;
  end;
end;

procedure TheObjectBTreeMapTest.TestKeys;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Keys do begin
      AssertEquals('V', Value2Int(A[J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheObjectBTreeMapTest.TestKeysReversed;
const N = 129;
var
  I, J: Integer;
  V: TKey;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.KeysReversed do begin
      AssertEquals('V', Value2Int(A[I - J]) - 1000, Key2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheObjectBTreeMapTest.TestValues;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.Values do begin
      AssertEquals('V', Value2Int(A[J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheObjectBTreeMapTest.TestValuesReversed;
const N = 129;
var
  I, J: Integer;
  V: TValue;
  A: array[0..N - 1] of TValue;
begin
  for I := 0 to N - 1 do begin
    A[I] := Int2Value(1000 + I);
    Map[Int2Key(I)] := A[I];
    J := 0;
    for V in Map.ValuesReversed do begin
      AssertEquals('V', Value2Int(A[I - J]), Value2Int(V));
      Inc(J);
    end;
    AssertEquals('J', I + 1, J);
  end;
end;

procedure TheObjectBTreeMapTest.TestGetRangeKeys;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TKey;
  begin
    I := 0;
    for V in Map.RangeKeys[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Key2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheObjectBTreeMapTest.TestGetRangeKeys;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [20, 25]);
      Verify(19, 30, [20, 25, 30]);
      Verify(19, 31, [20, 25, 30]);
      Verify(20, 29, [20, 25]);
      Verify(20, 30, [20, 25, 30]);
      Verify(20, 31, [20, 25, 30]);
      Verify(21, 29, [25]);
      Verify(21, 30, [25, 30]);
      Verify(21, 31, [25, 30]);

      Verify(19, 24, [20]);
      Verify(19, 25, [20, 25]);
      Verify(19, 26, [20, 25]);
      Verify(20, 24, [20]);
      Verify(20, 25, [20, 25]);
      Verify(20, 26, [20, 25]);
      Verify(21, 24, []);
      Verify(21, 25, [25]);
      Verify(21, 26, [25]);

      Verify(29, 19, [25, 20]);
      Verify(29, 20, [25, 20]);
      Verify(29, 21, [25]);
      Verify(30, 19, [30, 25, 20]);
      Verify(30, 20, [30, 25, 20]);
      Verify(30, 21, [30, 25]);
      Verify(31, 19, [30, 25, 20]);
      Verify(31, 20, [30, 25, 20]);
      Verify(31, 21, [30, 25]);

      Verify(24, 19, [20]);
      Verify(24, 20, [20]);
      Verify(24, 21, []);
      Verify(25, 19, [25, 20]);
      Verify(25, 20, [25, 20]);
      Verify(25, 21, [25]);
      Verify(26, 19, [25, 20]);
      Verify(26, 20, [25, 20]);
      Verify(26, 21, [25]);
    end;
end;

procedure TheObjectBTreeMapTest.TestGetRange;

  procedure Verify(const RangeFrom, RangeTo: Integer; const Expect: array of Integer);
  var
    I: Integer;
    V: TValue;
  begin
    I := 0;
    for V in Map.Range[Int2Key(RangeFrom), Int2Key(RangeTo)] do begin
      AssertEquals(Expect[I], Value2Int(V));
      Inc(I);
    end;
    AssertEquals(Length(Expect), I);
  end;

// procedure TheObjectBTreeMapTest.TestGetRange;
var A, B: Boolean;
begin
  for A in Boolean do
    for B in Boolean do begin
      TearDown;
      SetUp;
      if A then
        Map[Int2Key(10)] := Int2Value(100);
      Map[Int2Key(20)] := Int2Value(200);
      Map[Int2Key(25)] := Int2Value(250);
      Map[Int2Key(30)] := Int2Value(300);
      if B then
        Map[Int2Key(40)] := Int2Value(400);

      Verify(19, 29, [200, 250]);
      Verify(19, 30, [200, 250, 300]);
      Verify(19, 31, [200, 250, 300]);
      Verify(20, 29, [200, 250]);
      Verify(20, 30, [200, 250, 300]);
      Verify(20, 31, [200, 250, 300]);
      Verify(21, 29, [250]);
      Verify(21, 30, [250, 300]);
      Verify(21, 31, [250, 300]);

      Verify(19, 24, [200]);
      Verify(19, 25, [200, 250]);
      Verify(19, 26, [200, 250]);
      Verify(20, 24, [200]);
      Verify(20, 25, [200, 250]);
      Verify(20, 26, [200, 250]);
      Verify(21, 24, []);
      Verify(21, 25, [250]);
      Verify(21, 26, [250]);

      Verify(29, 19, [250, 200]);
      Verify(29, 20, [250, 200]);
      Verify(29, 21, [250]);
      Verify(30, 19, [300, 250, 200]);
      Verify(30, 20, [300, 250, 200]);
      Verify(30, 21, [300, 250]);
      Verify(31, 19, [300, 250, 200]);
      Verify(31, 20, [300, 250, 200]);
      Verify(31, 21, [300, 250]);

      Verify(24, 19, [200]);
      Verify(24, 20, [200]);
      Verify(24, 21, []);
      Verify(25, 19, [250, 200]);
      Verify(25, 20, [250, 200]);
      Verify(25, 21, [250]);
      Verify(26, 19, [250, 200]);
      Verify(26, 20, [250, 200]);
      Verify(26, 21, [250]);
    end;
end;

{ TheBTreeMapTest }

procedure TheBTreeMapTest.Done(const V: TValue);
begin
  Assert(@V = @V); // hint off
  // nop
end;

function TheBTreeMapTest.Int2Key(const N: Integer): TKey;
begin
  Assert(N = N); // hint off
  Initialize(Result); // hint off
  raise EAbstractError.Create(Format('%s.Int2Key', [ClassName]));
end;

function TheBTreeMapTest.Key2Int(const K: TKey): Integer;
begin
  Assert(@K = @K); // hint off
  Result := 0; // hint off
  raise EAbstractError.Create(Format('%s.Key2Int', [ClassName]));
end;

function TheBTreeMapTest.Int2Value(const N: Integer): TValue;
begin
  Assert(N = N); // hint off
  Initialize(Result); // hint off
  raise EAbstractError.Create(Format('%s.Int2Value', [ClassName]));
end;

function TheBTreeMapTest.Value2Int(const V: TValue): Integer;
begin
  Assert(@V = @V); // hint off
  Result := 0; // hint off
  raise EAbstractError.Create(Format('%s.Value2Int', [ClassName]));
end;

procedure TheBTreeMapTest.SetUp;
begin
  Map := TBTreeMap.Create;
end;

procedure TheBTreeMapTest.TearDown;
begin
  FreeAndNil(Map);
end;

procedure TheBTreeMapTest.TestCreate;
begin
  AssertEquals(0, Map.Count);
end;

procedure TheBTreeMapTest.TestCount;
begin
  AssertEquals('.Count', 0, Map.Count);
  Map[Int2Key(0)] := Int2Value(100);
  AssertEquals('.Count', 1, Map.Count);
  Done(Map.First);
  Map.Delete(Int2Key(0));
  AssertEquals('.Count', 0, Map.Count);
end;

procedure TheBTreeMapTest.TestMissingKeyValue;
begin
  AssertEquals('a) V[0]', Low(Integer), Value2Int(Map[Int2Key(0)]));
  AssertException('.MissingKeyValue', EMapKeyNotFound, @Map.RunInheritedMissingKeyValue);
  Map[Int2Key(0)] := Int2Value(100);
  AssertEquals('b) V[0]', 100, Value2Int(Map[Int2Key(0)]));
  Done(Map.First);
  Map.Delete(Int2Key(0));
  AssertEquals('c) V[0]', Low(Integer), Value2Int(Map[Int2Key(0)]));
end;

procedure TheBTreeMapTest.TestClear;
const N = 10;
var I: Integer;
begin
  for I := 0 to N - 1 do
    Map[Int2Key(I)] := Int2Value(10 * I);
  Map.Clear;
  AssertEquals('.Count', 0, Map.Count);
end;

procedure TheBTreeMapTest.TestFirst;
begin
  Map[Int2Key(100)] := Int2Value(1000);
  AssertEquals('b) .First', 1000, Value2Int(Map.First));
  Map[Int2Key(200)] := Int2Value(2000);
  AssertEquals('d) .First', 1000, Value2Int(Map.First));
end;

procedure TheBTreeMapTest.TestFirstKey;
begin
  Map[Int2Key(100)] := Int2Value(1000);
  AssertEquals('a) .First', 100, Key2Int(Map.FirstKey));
  Map[Int2Key(200)] := Int2Value(2000);
  AssertEquals('c) .First', 100, Key2Int(Map.FirstKey));
end;

procedure TheBTreeMapTest.TestLast;
begin
  Map[Int2Key(100)] := Int2Value(1000);
  AssertEquals('b) .Last', 1000, Value2Int(Map.Last));
  Map[Int2Key(200)] := Int2Value(2000);
  AssertEquals('d) .Last', 2000, Value2Int(Map.Last));
end;

procedure TheBTreeMapTest.TestLastKey;
begin
  Map[Int2Key(100)] := Int2Value(1000);
  AssertEquals('a) .Last', 100, Key2Int(Map.LastKey));
  Map[Int2Key(200)] := Int2Value(2000);
  AssertEquals('c) .Last', 200, Key2Int(Map.LastKey));
end;

procedure TheBTreeMapTest.TestExtract;
var Item: TValue;
begin
  Initialize(Item); // hint off
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(0)] := Int2Value(1000);
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  AssertTrue(Map.Extract(Int2Key(0), Item));
  try
    AssertEquals('a1) .Count', 0, Map.Count);
    AssertEquals('a3) Item', 1000, Value2Int(Item));
  finally
    Done(Item);
  end;
  TearDown;

  Setup;
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(0)] := Int2Value(1000);
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(1)] := Int2Value(1001);
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  AssertTrue(Map.Extract(Int2Key(0), Item));
  try
    AssertEquals('b1) .Count', 1, Map.Count);
    AssertEquals('b3) Item', 1000, Value2Int(Item));
  finally
    Done(Item);
  end;
  AssertEquals('b4) Item', 1, Key2Int(Map.FirstKey));
  AssertEquals('b5) Item', 1001, Value2Int(Map.First));
  TearDown;

  Setup;
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(0)] := Int2Value(1000);
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(1)] := Int2Value(1001);
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  AssertTrue(Map.Extract(Int2Key(1), Item));
  try
    AssertEquals('c1) .Count', 1, Map.Count);
    AssertEquals('c3) Item', 1001, Value2Int(Item));
  finally
    Done(Item);
  end;
  AssertEquals('c4) Item', 0, Key2Int(Map.FirstKey));
  AssertEquals('c5) Item', 1000, Value2Int(Map.First));
  TearDown;

  Setup;
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(0)] := Int2Value(1000);
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(1)] := Int2Value(1001);
  AssertFalse(Map.Extract(Int2Key(-1), Item));
  Map[Int2Key(2)] := Int2Value(1002);
  AssertTrue(Map.Extract(Int2Key(1), Item));
  try
    AssertEquals('d1) .Count', 2, Map.Count);
    AssertEquals('d3) Item', 1001, Value2Int(Item));
  finally
    Done(Item);
  end;
  AssertEquals('d4) Item', 0, Key2Int(Map.FirstKey));
  AssertEquals('d5) Item', 1000, Value2Int(Map.First));
  AssertEquals('d6) Item', 2, Key2Int(Map.LastKey));
  AssertEquals('d7) Item', 1002, Value2Int(Map.Last));
end;

procedure TheBTreeMapTest.TestDelete;
var Item: TValue;
begin
  Map[Int2Key(0)] := Int2Value(1000);
  Done(Map.First);
  Map.Delete(Int2Key(0));
  AssertEquals('a1) .Count', 0, Map.Count);
  TearDown;

  SetUp;
  Map[Int2Key(0)] := Int2Value(1000);
  Map[Int2Key(1)] := Int2Value(1001);
  Done(Map.First);
  Map.Delete(Int2Key(0));
  AssertEquals('b1) .Count', 1, Map.Count);
  AssertEquals('b2) Item', 1, Key2Int(Map.FirstKey));
  AssertEquals('b3) Item', 1001, Value2Int(Map.First));
  TearDown;

  SetUp;
  Map[Int2Key(0)] := Int2Value(1000);
  Map[Int2Key(1)] := Int2Value(1001);
  Done(Map[Int2Key(1)]);
  Map.Delete(Int2Key(1));
  AssertEquals('c1) .Count', 1, Map.Count);
  AssertEquals('c2) Item', 0, Key2Int(Map.FirstKey));
  AssertEquals('c3) Item', 1000, Value2Int(Map.First));
  TearDown;

  SetUp;
  Map[Int2Key(0)] := Int2Value(1000);
  Map[Int2Key(1)] := Int2Value(1001);
  Map[Int2Key(2)] := Int2Value(1002);
  Done(Map[Int2Key(1)]);
  Map.Delete(Int2Key(1));
  AssertEquals('d1) .Count', 2, Map.Count);
  AssertEquals('c2) Item', 0, Key2Int(Map.FirstKey));
  AssertEquals('c3) Item', 1000, Value2Int(Map.First));
  AssertEquals('d4) Item', 2, Key2Int(Map.LastKey));
  AssertEquals('d5) Item', 1002, Value2Int(Map.Last));
  Assert(@Item = @Item); // hint off
end;

procedure TheBTreeMapTest.TestMap;
var
  A: array[0..129] of TKey;
  I, J: Integer;
begin
  for I := Low(A) to High(A) do begin
    A[I] := Int2Key(I xor $AAAA);
    Map[A[I]] := Int2Value(1000 + I);
    for J := Low(A) to I do
      AssertEquals('V', 1000 + J, Value2Int(Map[A[J]]));
  end;
  Assert(@A = @A); // hint off
end;

procedure TheBTreeMapTest.TestGet;
var V: TValue;
begin
  Initialize(V); // hint off
  AssertFalse(Map.Get(Int2Key(0), V));
  AssertFalse(Map.Get(Int2Key(1), V));
  AssertFalse(Map.Get(Int2Key(2), V));
  Map[Int2Key(0)] := Int2Value(1000);
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(1000, Value2Int(V));
  AssertFalse(Map.Get(Int2Key(1), V));
  AssertFalse(Map.Get(Int2Key(2), V));
  Map[Int2Key(2)] := Int2Value(1002);
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(1000, Value2Int(V));
  AssertFalse(Map.Get(Int2Key(1), V));
  AssertTrue(Map.Get(Int2Key(2), V));
  AssertEquals(1002, Value2Int(V));
end;

procedure TheBTreeMapTest.TestPut;
var V, V2: TValue;
begin
  Initialize(V); // hint off
  AssertFalse(Map.Put(Int2Key(0), Int2Value(1000), False));
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(1000, Value2Int(V));
  TearDown;

  SetUp;
  AssertFalse(Map.Put(Int2Key(0), Int2Value(1000), True));
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(1000, Value2Int(V));
  TearDown;

  SetUp;
  AssertFalse(Map.Put(Int2Key(0), Int2Value(1000), False));
  V2 := Int2Value(-1000);
  try
    AssertTrue(Map.Put(Int2Key(0), V2, False));
  finally
    Done(V2);
  end;
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(1000, Value2Int(V));
  Done(V);
  AssertTrue(Map.Put(Int2Key(0), Int2Value(-1000), True));
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(-1000, Value2Int(V));
end;

procedure TheBTreeMapTest.TestPut2;
var V, V2, Prev: TValue;
begin
  Initialize(Prev); // hint off
  Initialize(V); // hint off
  AssertFalse(Map.Put(Int2Key(0), Int2Value(1000), Prev, False));
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(1000, Value2Int(V));

  V2 := Int2Value(-1000);
  try
    AssertTrue(Map.Put(Int2Key(0), V2, Prev, False));
  finally
    Done(V2);
  end;
  AssertEquals(1000, Value2Int(Prev));
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(1000, Value2Int(V));

  AssertTrue(Map.Put(Int2Key(0), Int2Value(-1000), Prev, True));
  try
    AssertEquals(1000, Value2Int(Prev));
  finally
    Done(Prev);
  end;
  AssertTrue(Map.Get(Int2Key(0), V));
  AssertEquals(-1000, Value2Int(V));
end;

procedure TheBTreeMapTest.TestMix;
const
  N = 32;
  XORS: array[0..3] of Cardinal = (0, $FFFFFFFF, $55555555, $AAAAAAAA);
var
  KIndex, KData, Cycle, XorI, IPut, IGet: Cardinal;
  V, V2: TValue;
begin
  Initialize(V); // hint off
  TearDown;
  for KIndex := 2 to 3 do
    for KData := 1 to 2 do
      for Cycle := 1 to N do
        for XorI := Low(XORS) to High(XORS) do begin
          Map := TBTreeMap.Create(KIndex, KData);
          try

            AssertTrue('p', Map.Count = 0);

            // fill
            for IPut := 1 to Cycle do begin
              AssertFalse('q', Map.Put(Int2Key(Integer(IPut xor XORS[XorI])), Int2Value(IPut)));
              AssertEquals(IPut, Map.Count);
            end;

            // verify
            for IGet := 1 to Cycle do begin
              AssertTrue('s', Map.Get(Int2Key(Integer(IGet xor XORS[XorI])), V));
              AssertEquals(IGet, Value2Int(V));
            end;

            // refill w/o overwrite
            for IPut := 1 to Cycle do begin
              V2 := Int2Value(Integer(not IPut));
              try
                AssertTrue('u', Map.Put(Int2Key(Integer(IPut xor XORS[XorI])), V2, V, False));
              finally
                Done(V2);
              end;
              AssertEquals(IPut, Value2Int(V));
            end;
            AssertTrue('w', Map.Count = Cycle);

            // verify
            for IGet := 1 to Cycle do begin
              AssertTrue('s', Map.Get(Int2Key(Integer(IGet xor XORS[XorI])), V));
              AssertEquals(IGet, Value2Int(V));
            end;

            // refill with overwrite
            for IPut := 1 to Cycle do begin
              AssertTrue('z', Map.Put(Int2Key(Integer(IPut xor XORS[XorI])), Int2Value(Integer(not IPut)), V));
              try
                AssertEquals(IPut, Value2Int(V));
              finally
                Done(V);
              end;
            end;
            AssertTrue('1', Map.Count = Cycle);

            // verify
            for IGet := 1 to Cycle do begin
              AssertTrue('s', Map.Get(Int2Key(Integer(IGet xor XORS[XorI])), V));
              AssertEquals(Integer(not IGet), Value2Int(V));
            end;

            // empty
            for IGet := 1 to Cycle do begin
              AssertTrue('4', Map.Extract(Int2Key(Integer(IGet xor XORS[XorI])), V));
              try
                AssertEquals(Integer(not IGet), Value2Int(V));
              finally
                Done(V);
              end;
              AssertEquals(Cycle - IGet, Map.Count);
            end;
            AssertTrue('7', Map.Count = 0);

          finally
            TearDown;
          end;
        end;
end;

initialization
  RegisterTests([
    TheIntBTreeMapTest,
    TheStrBTreeMapTest,
    TheIntCmpBTreeMapTest,
    TheStrCmpBTreeMapTest,
    TheInterfaceCmpBTreeMapTest,
    TheObjectBTreeMapTest
  ]);

end.

